백준 1520번 - 내리막 길

문제링크

풀이과정

높이가 더 낮은 부분으로 이동하면서 특정 지점까지 가야하는 경로의 수를 구하는 문제이다.
BFS만을 사용하는 문제처럼 가장 짧은 경로를 구하는 것이 아닌, 모든 경우의 수를 구하는 문제이기 때문에, dp와 dfs를 결합하여 풀 수 있지 않을 까 했다

BFS vs DFS

bfs가 아닌 dfs를 사용하려했던 이유는 이동 경로가 다르면 다른 경우의 수가 되기 때문에, 경로를 기억할 수 있는 dfs 를 선택했다.
그래프 탐색 알고리즘(BFS,DFS)#BFS, DFS 선택 기준 참고.

중복 방문을 허용하기 위해서 visited를 사용하지 않았고, 지나온 길을 +1하면서 이동했다.

코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
rl.on("line", (line) => {
  input.push(line);
});

rl.on("close", () => {
  const [m, n] = input[0].split(" ").map((x) => parseInt(x));
  const map = [];
  const d = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  for (let i = 0; i < m; i++) {
    map.push(input[i + 1].split(" ").map((x) => parseInt(x)));
  }

  const dp = Array.from(Array(m), () => Array(n).fill(0));
  const stack = [];
  stack.push([0, 0]);
  dp[0][0] = 1;
  while (stack.length > 0) {
    const [x, y] = stack.pop();
    for (const [dx, dy] of d) {
      const [newx, newy] = [x + dx, y + dy];
      if (isInRange(newx, newy) && map[x][y] > map[newx][newy]) {
        stack.push([newx, newy]);
        dp[newx][newy] += 1;
      }
    }
  }
  function isInRange(x, y) {
    return x >= 0 && x < m && y >= 0 && y < n;
  }
  console.log(dp[m - 1][n - 1]);
});

시간초과 가 발생했다.
사실 위의 코드는 DP와 DFS를 결합한 방법이 아닌, 모든 경우의 수를 DFS를 사용하여 찾은 방법이다.
심지어 중복 방문을 체크하지 않았기 때문에 시간복잡도가 엄청나게 커진다.

다른 방법.

BFS, DFS에 극한 되지 않고, 해결할 수 있는 방법을 생각해봤다.
각 위치에 갈 수 있는 경우의 수를 저장한 뒤에 4방면으로 이동가능하면 더해주는 식의 DP라고 할 수 있는 방법을 생각해냈다.
약간의 난관에 부딪혔다. 일반적인 순회로는 경우의 수를 정확하게 더해줄 수 없다.
Attachments/Picture/Pasted image 20240215170105.png|300
일반적인 순회(파란색)의 경우에는 20까지 가는 경우의 수를 1로 계산하지만, 우리는 빨간색처럼 20까지의 경우의 수를 2로 계산해야한다.

그래서 이를 해결하기 위해 높이가 큰 순서대로 순회하기로 했다.
높이를 기준으로 내림차순 정렬을 한 뒤에 순회하면서 이동 가능한 4방면에 경우의 수를 더해줬다.

코드

시간초과가 발생하지 않고 잘 해결되었다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
rl.on("line", (line) => {
  input.push(line);
});

rl.on("close", () => {
  const [m, n] = input[0].split(" ").map((x) => parseInt(x));
  const map = [];
  const d = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  for (let i = 0; i < m; i++) {
    map.push(input[i + 1].split(" ").map((x) => parseInt(x)));
  }

  const arr = [];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      arr.push([i, j, map[i][j]]);
    }
  }
  arr.sort((a, b) => b[2] - a[2]);
  const dp = Array.from(Array(m), () => Array(n).fill(0));
  dp[0][0] = 1;
  for (const [x, y, h] of arr) {
    if (dp[x][y] == 0) {
      continue;
    }
    for (const [dx, dy] of d) {
      const [newx, newy] = [x + dx, y + dy];
      if (isInRange(newx, newy) && map[x][y] > map[newx][newy]) {
        dp[newx][newy] += dp[x][y];
      }
    }
  }
  console.log(dp[m - 1][n - 1]);

  function isInRange(x, y) {
    return x >= 0 && x < m && y >= 0 && y < n;
  }
});